
class _DoublyLinkedBase:
    class _Node:
        def __init__(self, element, prev, next):
            """
            包含前后节点的双向节点
            :param element:
            :param prev:
            :param next:
            """
            self._element = element
            self._prev = prev
            self._next = next

    def __init__(self):
        """Create an empty doubly linked list"""
        self._header: _DoublyLinkedBase._Node = self._Node(None, None, None)
        self._tailer: _DoublyLinkedBase._Node = self._Node(None, None, None)
        self._header._next = self._tailer
        self._tailer._prev = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def _insert_between(self, e, predecessor, successor):
        """Add element between of two existed nodes, and return the new node"""
        new_node = self._Node(e, predecessor, successor)
        predecessor._next = new_node
        successor._prev = new_node
        self._size += 1
        return new_node

    def _delete_node(self, node):
        """Delete node from the list and return its element"""
        predecessor = node._prev
        successor = node._next
        predecessor._next = successor
        successor._prev = predecessor

        self._size -= 1
        element = node._element
        node._prev = node._next = node._element = None
        return element

    def middle(self):
        """
        通过非计数的方法找到链表的中间位置(链表长度若为偶数返回左边的节点)
        :return:
        """
        if self.is_empty():
            raise Exception("doubly link list is empty")
        middle = self._header._next
        prev_node = self._tailer._prev
        while (middle != prev_node and middle._next != prev_node):
            middle = middle._next
            prev_node = prev_node._prev
        return middle

    def max(self):
        """Find max value of the list"""
        if self.is_empty():
            raise Exception("doubly link list is empty")
        best = walk = self._header._next
        while walk != self._tailer:
            if walk._element > best._element:
                best = walk
            walk = walk._next
        return best._element
